/**
 * 项目名称: Topic_311.cpp
 * 项目路径: study/DataStructure/LeetCode/树/中等
 * 编辑时间: 2024年08月17日08时52分48秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * 做题思路: 本题是验证二叉树的前序序列化,给定一个二叉树结点数组,
 * 我们只需模拟构造即可,模拟构造不成功,说明无法构建二叉树
 * 题目中给的结点,就是二叉树的每个结点
 * 不需要考虑二叉树前序序列构造二叉树的非唯一性
 */
class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n =preorder.length();
        int i =0;
        stack<int>stk;
        stk.push(1);
        while (i<n){
            if(stk.empty())return false;
            if(preorder[i] == ',')i++;
            else if(preorder[i] == '#'){
                stk.top() -=1;
                if(stk.top() == 0)stk.pop();
                i++;
            }else{
                //读取数字
                while (i<n&&preorder[i]!=',')i++;
                stk.top()-=1;
                if(stk.top()==0)stk.pop();
                stk.push(2);
            }
        }
        return stk.empty();
    }
};